package swardToOffer.struct_1_arr;

/**
 * @Author ChanZany
 * @Date 2021/5/24 16:09
 * @Version 1.0
 * 面试题42：连续子数组的最大和
 * 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整
 * 数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
 * 方法1:
 * 考虑用双指针来解决这类问题，
 * 初始化：left=right = 0;
 * 步骤：
 * 1. right++,然后计算路径和sum并更新max
 * 2. 当arr[right]+sum<0的时候，left=right=right+1,然后回到步骤1
   方法2:
    动态规划
    状态定义:dp[i]代表以元素nums[i]为结尾的连续子数组最大和
    转移方程:若dp[i-1]<=0,说明dp[i-1]对dp[i]无贡献或负贡献,即dp[i-1]+nums[i]<=nums[i]
        当dp[i-1]>0;dp[i]=dp[i-1]+nums[i]
        当dp[i-1]<=0;dp[i]=nums[i];
    初始状态:dp[0]=nums[0]
    返回值:返回dp列表中的最大值,代表全局最大值
 *
 */
public class GreatestSumOfSubarrays {
    public int maxSubArrayDP(int[] nums){
        int curSum = 0;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (curSum<=0) curSum=nums[i];
            else curSum += nums[i];
            res = Math.max(res,curSum);
        }
        return res;
    }

    public int maxSubArray(int[] nums) {
        int sum = 0, max = nums[0], left = 0, right = 0;
        while (left <= right && right < nums.length) {
            if (sum < 0) {
                sum = 0;
                left = right;
                continue;
            }
            sum += nums[right++];
            max = Math.max(sum, max);
        }

        return max;
    }

    public static void main(String[] args) {
        GreatestSumOfSubarrays Main = new GreatestSumOfSubarrays();
        System.out.println(Main.maxSubArrayDP(new int[]{1, -2, -3, 4}));
        System.out.println(Main.maxSubArrayDP(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
        System.out.println(Main.maxSubArrayDP(new int[]{-1}));
    }
}
